\section{Identity based crypto}

Asymetrické kryptovacie systémy, ktoré veľmi dobre poznáme, vyžadujú,
aby si každý vygeneroval vlastnú inštanciu danej schémy. Problém pri
takomto riešení je distribúcia verejného kľúča. Ak nemáme dostatočne
dôveryhodný kanál na distribúciu môjho verejného kľúča, útočník si
môže pripraviť vlastný kľúč a presvedčiť obeť o tom, že je to môj
kľúč. Navyše, existujú isté ťažkosti s udržiavaním verejných kľúčov a
limity sú aj v chápanlivosti ľudí o potrebe bezpečného kanálu pri
distribúcii.
Isté riešenie tohoto problému,
ktoré sa ujalo najmä pri webových aplikáciach sú certifikáty --
kľúč sa podpíše dôveryhodnou autoritou a každý si môže
overiť, že po kanáli dostal správny kľúč. V tejto kapitole sa budeme
venovať alternatívnemu riešeniu -- verejným kľúčom bude priamo moja
identita.

Ako si to teda môžeme predstaviť? Nebudeme generovať inštanciu schémy,
ale uvažujme rovno, že mojím kľúčom bude priamo moja identifikácia -
či už email, OpenID konto a pod.

Na pomoc si ale budeme musieť prizvať dôveryhodnú tretiu stranu $M$.
Táto strana bude mať 2 kľúče master public key $M_{pk}$ a master
secret key $M_{sk}$. Túto tretiu stranu budeme potrebovať, aby nám
vygenerovala náš súkromný kľúč k môjmu verejnému kľúču (kontu).
Formálne, toto generovanie si môžeme popísať ako algoritmus, ktorý
užívateľovi $U$ priradí na záklede jeho identity $ID_U$ jeho súkromný
kľúč $U_{sk} = Extract(M_{sk}, ID_U)$. Samozrejme, kľúč ešte treba
dôveryhodne doručiť, toto ale nebudeme riešiť.

Potom môžeme šifrovať a dešifrovať nasledovne:
$c=E(m,ID_U,M_{pk})$ a opačne $m = D(c, U_{sk}, M_{pk})$, pričom
samozrejme požadujeme
$\forall ID_U \forall m: D(E(m, ID_U, M_{pk}), Extract(M_{sk},ID_U),
M_{pk})=m$.

Takáto schéma má ale výraznú bezpečnostnú slabinu - kompromitácia
$M_{sk}$ je fatálna. Je teda otázne, do akej miery môžeme dôverovať
zabezpečeniu dôveryhodnej strany. Napriek tomuto problému si ukážeme,
ako môže taká schéma fungovať.

\subsection{Cocksova schéma (2001)}

Bezpečnosť Coksovej schémy \cite{cocks} sa opiera o problém rozlišovania medzi
štvorcami a preudoštvorcami. Presnejšie povedané,
nech $n=pq$ kde $p,q$ sú prvočísla také, že $p \equiv q \equiv 3 \pmod{4}$.

\def\jacobi#1#2{\left( \frac{#1}{#2} \right)}

Nás budú zaujímať také čísla $x$, pre ktoré Jakobiho symbol
$\jacobi{x}{n} =1$. Jakobiho symbol totiž vieme počítať aj bez
faktorizácie $n$, na druhú stranu, overiť, či $x$ je štvorec alebo len
pseudoštvorec nie je ľahko rozhodnuteľné.

\begin{figure}[h]
    \centering
    \includegraphics{img/10/jacobi.1.mps}
    \caption{Jakobiho symbol pre $n=pq$}
    \label{fig:jacobi}
\end{figure}


Schéma pre dôveryhodnú tretiu stranu bude nasledovná
\begin{itemize}
    \item $M_{pk}: \langle n \rangle$
    \item $M_{sk}: \langle p,q \rangle$
    \item Extract: $h: \{0,1\}^* \mapsto (QR_n \union QNR_n^{+1})$,
    kde $h$ bude dobrá hashovacia funkcia.
\end{itemize}

Najskôr by sme si mali overiť, že vieme ľahko vytvoriť dobrú
hashovaciu funkciu. Uvažujme, že máme kvalitnú hašovaciu funkciu
$h:\{0,1\}^* \mapsto Z_n$.
Potom túto funkciu vieme veľmi jednoducho transformovať, aby išla do
zúženého definičného oboru nasledovným spôsobom.

Zvoľme si $a \in Z_n$ také, že $\jacobi{a}{n} = -1$. Na tomto mieste
poznamenajme, že $a$ nie je náhodné, ba priam musí byť fixné, inak by
účastníci nevedeli počítať hash.
Jednoduché pozorovanie je, že ak $\jacobi{h(x)}{n}=-1$,
potom $\jacobi{a h(x)}{n}=1$.
Tým pádom funkcia
\begin{equation*}
h'(x) = \begin{cases}
            h(x)   \quad &\jacobi{h(x)}{n}=1 \\
            a h(x) \quad &\jacobi{h(x)}{n}=-1
        \end{cases}
\end{equation*}
je dobrým kandidátom na hashovaciu funkciu
$\{0,1\}^* \mapsto (QR_n \union QNR_n^{+1})$.

Priradenie kľúčov identite bude prebiehať nasledovne:
\begin{itemize}
    \item $U_{pk}=h(ID_U)$

    \item $U_{sk}^2=\begin{cases}
            \phantom{-} U_{pk}\pmod{n}  \quad& U_{pk} \in QR_n \\
                     -  U_{pk}\pmod{n}  \quad& U_{pk} \in QNR_n^{+1}
                    \end{cases}$
\end{itemize}

\begin{poznamka}
    Dá sa ukázať, že výpočet $U_{sk}$ možno previesť ako
    $U_{sk} = (\pm a)^{(n + 5 - p - q)/8}$, t.j. výpočet
    druhej odmocniny je efektívny.
\end{poznamka}

\noindent
Šifrovanie:
\begin{itemize}
    \item Správa je $m\in\{-1,1\}$
    \item Náhodne zvolíme $t_1,t_2$ tak aby platilo
            $\jacobi{t_1}{n} = \jacobi{t_2}{n} = m$
    \item $y_1 = t_1 + U_{pk} t_1^{-1} \pmod{n}$
    \item $y_2 = t_2 - U_{pk} t_2^{-1} \pmod{n}$.\footnote{
            Pozor -- zmena v znamienku}
    \item $E(m) = \langle y_1, y_2 \rangle$.
\end{itemize}


\noindent
Dešifrovanie:

\begin{poznamka}
    Ako sa o chvíľu ukáže, naša dešifrovacia funkcia
    nebude formálne fungovať ako $D(c,U_{sk}, M_{pk})$.
    Čitateľovi, ktorému sa nechce zahrať hru ``nájdi 5 rozdielov''
    môžeme zahintiť, že na dešifrovanie bude potrebovať aj identitu
    účastníka, za ktorého to dešifruje, resp. presnejšie povedané bude
    potrebovať verejný kľúč $U_{pk}$ ktorý sa dá získať ako hash
    identity. Správne by teda malo byť $D(c,U_{sk},U_{pk}, M_{pk})$.
\end{poznamka}

Základom bude počítanie Jakobiho symbolu tvaru $\jacobi{y +2 U_{sk}}{n}$.
Budeme rozlišovať 2 prípady (a práve na to potrebujeme aj verejný kľúč):
\begin{itemize}
    \item $U_{sk}^2 \equiv U_{pk}$.
        Vypočítame Jakobiho symbol $\jacobi{y_1 + 2U_{sk}}{n}$.
        \begin{align*}
            \jacobi{y_1 + 2U_{sk}}{n} &=
            \jacobi{t_1 + U_{pk} t_1^{-1} + 2 U_{sk}}{n} =
            \jacobi{t_1 + U_{sk}^2 t_1^{-1} + 2 U_{sk}}{n} \\
            &=
            \jacobi{t_1(1 + U_{sk}^2 t_1^{-2} + 2 t_1^{-1} U_{sk})}{n} =
            \jacobi{t_1(1+U_{sk}t_1^{-1})^2}{n}  \\
            &=
            \jacobi{t_1}{n} \cdot \jacobi{(1+U_{sk}t_1^{-1})^2}{n}=
            \jacobi{t_1}{n} \cdot 1 \\
            &= m
        \end{align*}

    \item $U_{sk}^2 \equiv -U_{pk}$.
        Vypočítame Jakobiho symbol $\jacobi{y_2 + 2U_{sk}}{n}$.
        \begin{align*}
            \jacobi{y_2 + 2U_{sk}}{n} &=
            \jacobi{t_2 - U_{pk} t_2^{-1} + 2 U_{sk}}{n} =
            \jacobi{t_2 + U_{sk}^2 t_2^{-1} + 2 U_{sk}}{n} \\
            &=
            \jacobi{t_2(1 + U_{sk}^2 t_2^{-2} + 2 t_2^{-1} U_{sk})}{n}
            \\
            &=
            \jacobi{t_2}{n} \cdot \jacobi{(1+U_{sk}t_2^{-1})^2}{n} \\
            &= m
        \end{align*}
\end{itemize}

Čo sa týka praktickej realizácie takejto schémy, výpočtové nároky sú
veľmi nízke. Ak máme správu dĺžky $l$, tak
šifrovanie pozostáva z $l$ operácii počítania Jakobiho
symbolu a delenia, dešifrovanie je $l$-krát výpočet Jakobiho symbolu.
Pre typické parametre ako $n=1024 \unit{bit}$ a $l=128$ je očakávateľné, že
potrebný čas bude menší ako na jedinú exponenciáciu. Preto jedinou
reálnou otázkou ostáva veľkosť správy, ktorá v tomto prípade narastie
na $32KB$.

\subsubsection{Bezpečnosť schémy}
V prvom rade, je evidentné, že ak útočník pozná faktorizáciu $M_{pk}$,
systém považujeme za zlomený. Proti tomuto problému sa dá brániť
rôznymi spôsobmi, Cocks v svojom článku navrhol spôsob bezznalostného
spoločného výpočtu viacerých dôveryhodných autorít (tým pádom $M_{sk}$
nemusí byť prítomné naraz na jednom mieste).

V ďalšom teda budeme predpokladať, že útočník nepozná faktorizáciu $M_{pk}$.

Predpokladajme nateraz, že $U_{sk}^2 \equiv U_{pk}$.
Ukážeme, že z pohľadu útočníka nenesie $y_2$ žiadnu informáciu o tom, ako
vyzerá $m$.

Nech $y = t - U_{pk} t^{-1} \pmod{n}$.
Potom
\begin{equation*}
    t^2 - y t - U_{pk} \equiv 0 \pmod{n}
\end{equation*}
a teda špeciálne
\begin{equation*}
    t^2 - y t - U_{pk} \equiv 0 \pmod{p}
\end{equation*}
Dostali sme kvadratickú rovnicu nad poľom $Z_p$ a teda riešením sú 2 korene
$r_1,r_2$.
Dostávame teda
%% netusim, ako presvedcit align na to, aby pmod zarovnal vlavo
\begin{alignat*}{3}
    (t-r_1)(t-r_2) &\equiv t^2 - y t - U_{pk} &\pmod{n}\\
    r_1 r_2 &\equiv -U_{pk} &\pmod{p}
\end{alignat*}
%
Ak vypočítajme Jakobiho symbol $\jacobi{r_1}{p} \jacobi{r_2}{p}$,
dostaneme hodnotu 
\begin{equation*}
    \jacobi{r_1}{p}\jacobi{r_2}{p} = \jacobi{r_1 r_2}{p} =
    \jacobi{-U_{pk}}{p} = \jacobi{-1}{p} \jacobi{U_{sk}^2}{p}=-1\cdot 1=-1
\end{equation*}
nakoľko platí $\jacobi{-1}{p}=-1$ za predpokladu $p \equiv 3 \pmod{4}$.

\begin{poznamka}[Stanekova básnická otázka na publikum: čo ak sú
    niektoré 2 korene rovnaké?]
    Odpoveď: Také neexistujú. Dôvod:
    Zoberme $r_1 r_2 \equiv -U_{pk} \pmod{p}$, dostaneme $r^2 \equiv
    -U_{pk} \pmod{p}$, $U_{sk}^2 \equiv U_{pk} \pmod{p}$. Teda
    $U_{pk}, -U_{pk} \in QR_p$, čo je spor, pretože za predpokladu 
    $p\equiv 3 \pmod{4}$ je rezíduum práve jedno z nich.

    Skrátene povedané $r^2$ nemôže byť kvadratické nerezíduum.
\end{poznamka}

To isté môžeme zistiť modulo $q$.
Skombinovaním jednotilivých riešení modulo $p,q$ dostaneme 4 riešenia
modulo $n$, tieto riešenia (označme ich $t_{--}, t_{-+}, t_{+-},
t_{++}$) budú v 4 rôznych kvadrantoch 
(obr. \ref{fig:jacobi}). Nuž ale to sme doma.
Chceli by sme ukázať, že znalosť $y_2$ neovplyvní pravdepodobnosť, že
správa nadobúda istú hodnotu, t.j.
$Pr[m=m_0]=Pr[m=m_0 | y=y_2]$.
To je podľa Bayessovej vety
\begin{equation*}
    Pr[m=m_0 | y=y_2] = \frac{Pr[y=y_2 | m=m_0] \cdot Pr[m=m_0]}{Pr[y=y_2]}
\end{equation*}
No a evidentne (pretože $t$ volíme náhodne a rovnomerne)
platí $Pr[y=y_2 | m=+1] =2/J_{+}(n)$ a $Pr[y=y_2 | m=-1] = 2/J_{-}(n)$
kde $J_{+},J_{-}$ označuje počet čísel s Jakobiho symbolom $+1$ resp. $-1$. 

My však vieme, že $J_{+}(n) = J_{-}(n) = (p-1)(q-1)/2$ a teda
$Pr[y=y_2| m=+1] = Pr[y=y_2 | m=-1] = Pr[y=y_2]$. Tým sme ale ukázali,
že $Pr[m=m_0] = Pr[m=m_0 | y=y_2]$ a teda $y_2$ naozaj nič nevypovedá
o hodnote $m$.

\medskip
Teraz ukážeme bezpečnosť schémy. Predpokladajme, že útočník vie riešiť
inštancie tejto schémy, našim cieľom je ukázať, že by potom vedel
riešiť problém kvadratickej reziduity $\pmod{n}$.
Majme $A \in Z_n^*$ také, že $\jacobi{a}{n}=1$. Chceli by sme vedieť
odpoveď na otázku, či $a$ je štvorec alebo pseudoštvorec.

Postupujme nasledovne
\begin{enumerate}
    \item zvolíme $m \inr \{-1,1\}$.
    \item zvolíme $t \inr Z_n^*: \jacobi{t}{n}=m$, a vypočítame
        $y_1 = t + a t^{-1} \pmod{n}$.
    \item $y_2$ nebude vôbec závisieť od predchádzajúcich hodnôt,
            $y_2 = t -  t^{-1} \pmod{n}$, kde $t \inr Z_n^*$.
            Teda Jakobiho symbol $\jacobi{t}{n} \inr \{-1,1\}$.
            Poznámka: Stanek pôvodne prednášal $y_2 \inr Z_n^*$,
            čo má ale evidentný problém a to menovite, že pre $y_2$
            nemusí existovať riešenie. Lenže my chceme vygenerovať
            náhodnú inštanciu schémy a preto to riešenie musí mať.
    \item $m' \assign Attack(c=\langle y_1, y_2 \rangle, U_{pk}=a,M_{pk}=n)
            $.
    \item Pýtajme sa otázku $m'=m$?
\end{enumerate}
Teraz podľa kvadratickej reziduity $a$ môžeme dostať 2 rôzne
(pravdepodobnosti výsledkov).
\begin{itemize}
    \item Ak $a \in QR_{n}$, potom z $y_2$ program nemôže usúdiť nič,
    ako sme si vopred povedali a z $y_1$ by nám mal teda vypočítať
    $m$. Keďže sme predpokladali, že $Attack$ vie riešiť inštancie
    schémy, dostávame, že $Pr[m=m'] \ge 1/2 + \delta$.

    \item Ak $a \in QNR_{n}^{+1}$, potom nevieme nič usúdiť z $y_1$.
    Čiže chceme vypočítať $m$ z $y_2$. Lenže $y_2$ sme položili
    náhodne a teda pravdepodobnosť uhádnutia $m$ je $Pr[m=m'] = 1/2$.
\end{itemize}
Vidíme teda, že v týchto dvoch prípadoch sa nám pravdepodobnosti líšia
aspoň o $\delta$. To je pozitívne, pretože zopakovaním tohoto testu
niekoľko krát vieme s vysokou pravdepodobnosťou určiť reziduitu $a$.

Teda, je tu ešte jeden drobný háčik. Keďže nevieme povedať nič o
správaní (teda, hlavne úspešnosti) útočníkovej funkcie $Attack$
na nerovnomernej distribúcii vstupov (a pre fixné $a$ to je určite
nerovnomerná distribúcia), musíme nejakým spôsobom znáhodniť aj toto.
Samozrejme, nechceme pritom prijsť o informáciu, v akom vzťahu je
reziduita $a'$ a reziduita $a$.

\begin{lema}
    Nech $n=p,q$, kde $p,q$ sú prvočísla $p\equiv q\equiv 3 \pmod{4}$.
    Potom $a \in QR_n \iff -a \in QNR_n^{+1}$.
\end{lema}
\begin{dokaz}
    Už sme si povedali, že pre prvočísla kongruentné $3\pmod{4}$ to
    platí. No ale potom, ak $a$ bolo $QR_n$, tak
    $\jacobi{a}{p} = \jacobi{a}{q} =1$ a teda
    $\jacobi{-a}{p} = \jacobi{-a}{q} = -1$, čiže $-a$ je
    pseudoštvorec. Opačne to dokážeme podobne.
\end{dokaz}

Nuž ale potom stačí zvoliť
$a' = a b^2 z$, kde $b \inr Z_n^*$ a $z\inr\{-1,1\}$. 
Čitateľ si môže rozmyslieť, že $a'$ bude rovnomerne distribuované
$\inr Z_n^*$, a že budeme vedieť vzájomný vzťah kvadratickej reziduity
$a$ a $a'$. Tým pádom ale môžeme náš test zopakovať koľkokrát
potrebujeme a teda s vysokou pravdepodobnosťou budeme vedieť odlíšiť
kvadratické rezíduá a presudoprvočísla.

Ďalšou evidentnou bezpečnosťou slabinou schémy, ako sme ju tu
popísali, je možnosť útočníka zmeniť (nastaviť na konkrétnu hodnotu) jednotlivé vity správy podľa
ľubovôle. Preto je vhodné za správu pripojiť aj hash hodnotu na
kontrolu integrity, alebo iným spôsobom zaručiť nemanipulovateľnosť
jednotlivých bitov.
